package algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * Description TODO
 *
 * @ClassName algorithm.sort.HeapSort
 * @Version 1.0
 * @Date: 2022/2/18 13:58
 * @Author xuyi
 */
public class HeapSort {
    @Test
    public void test1(){
        int[] arr = generateRandomArray(10,20);
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        for(int i=arr.length-1; i>=0; i--){
            makeDump(arr,0,i);
            swap(arr,0,i);
        }
    }

    private void makeDump(int[] arr,int L,int R){
        for(int i=L+1;i<=R;i++){
            dump(arr,i);
        }
    }

    private void dump(int[] arr,int i){
        if(i<=0){
            return;
        }
        int parent;
        if(i%2==0){
            parent = (i-1)/2;
        }else{
            parent = i/2;
        }
        if(arr[parent]<arr[i]){
            swap(arr,i,parent);
            dump(arr,parent);
        }
    }

    private void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }
}
